In a private set intersection (PSI) protocol, a client having a set X1 and a server having a set X2 jointly compute the intersection of their respective private input sets in a manner that, at the end, the client learns the intersection and the server learns nothing. Existing private set intersection protocols require communication that is linear in the sizes of the sets, that is, they incur communication cost of O(|X1|+|X2|). This cost is prohibitive when the interactions between the client and the server are frequent, especially when the server stores a large data set. For example, the costs are particularly prohibitive for a smart phone privately checking the validity of a user's credentials against a database that contains millions of elements.
Thus, a need exists for lightweight set membership techniques wherein the communication cost is sublinear in the size of the sets held by the client and the server.